Interleaving string

Time: O(MxN); Space: O(M+N); hard

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”

Output: True

Example 2:

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”

Output: False

1.

[1]:

class Solution1(object):
    """
    Time: O(M*N)
    Space: O(M+N)
    """
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: a boolean
        """
        if len(s1) + len(s2) != len(s3):
            return False

        if len(s1) > len(s2):
            return self.isInterleave(s2, s1, s3)

        match = [False for i in range(len(s1) + 1)]
        match[0] = True

        for i in range(1, len(s1) + 1):
            match[i] = match[i -1] and s1[i - 1] == s3[i - 1]

        for j in range(1, len(s2) + 1):
            match[0] = match[0] and s2[j - 1] == s3[j - 1]
            for i in range(1, len(s1) + 1):
                match[i] = (match[i - 1] and s1[i - 1] == s3[i + j - 1]) \
                        or (match[i] and s2[j - 1] == s3[i + j - 1])

        return match[-1]

[2]:

s = Solution1()

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
assert s.isInterleave(s1, s2, s3) == True

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
assert s.isInterleave(s1, s2, s3) == False

2. Dynamic Programming

[3]:

class Solution2(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: a boolean
        """
        if len(s1) + len(s2) != len(s3):
            return False

        match = [[False for i in range(len(s2) + 1)] for j in range(len(s1) + 1)]
        match[0][0] = True

        for i in range(1, len(s1) + 1):
            match[i][0] = match[i - 1][0] and s1[i - 1] == s3[i - 1]

        for j in range(1, len(s2) + 1):
            match[0][j] = match[0][j - 1] and s2[j - 1] == s3[j - 1]

        for i in range(1, len(s1) + 1):
            for j in range(1, len(s2) + 1):
                match[i][j] = (match[i - 1][j] and s1[i - 1] == s3[i + j - 1]) \
                           or (match[i][j - 1] and s2[j - 1] == s3[i + j - 1])

        return match[-1][-1]

[4]:

s = Solution2()

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
assert s.isInterleave(s1, s2, s3) == True

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
assert s.isInterleave(s1, s2, s3) == False

3. Recursive + Hash

[5]:

class Solution3(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: a boolean
        """
        self.match = {}
        if len(s1) + len(s2) != len(s3):
            return False
        return self.isInterleaveRecu(s1, s2, s3, 0, 0, 0)

    def isInterleaveRecu(self, s1, s2, s3, a, b, c):
        if repr([a, b]) in self.match.keys():
            return self.match[repr([a, b])]

        if c == len(s3):
            return True

        result = False
        if a < len(s1) and s1[a] == s3[c]:
            result = result or self.isInterleaveRecu(s1, s2, s3, a + 1, b, c + 1)
        if b < len(s2) and s2[b] == s3[c]:
            result = result or self.isInterleaveRecu(s1, s2, s3, a, b + 1, c + 1)

        self.match[repr([a, b])] = result

        return result

[6]:

s = Solution3()

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
assert s.isInterleave(s1, s2, s3) == True

s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
assert s.isInterleave(s1, s2, s3) == False